package leetcode_day._2022._202201._0110;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/1/4 11:15
 * 猫和老鼠
 * 算法：动态规划
 */
public class _04_913 {
    static int N = 55;
    static int[][][] f = new int[2 * N * N][N][N];
    int[][] g;
    int n;
    public int catMouseGame(int[][] graph) {
        g = graph;
        n = graph.length;
        for (int i = 0; i < 2 * n * n; i++)
            for (int j = 0; j < n; j++) for (int k = 0; k < n; k++) f[i][j][k] = -1;
        return dfs(0, 1, 2);
    }
    int dfs(int k, int a, int b) {
        int ans = f[k][a][b];
        if (a == 0) ans = 1;
        else if (a == b) ans = 2;
        else if (k >= 2 * n * n) ans = 0;
        else if (ans == -1){
            if (k % 2 == 0) {
                boolean win = false, draw = false;
                for (int next : g[a]) {
                    int dfs = dfs(k + 1, next, b);
                    if (dfs == 1) win = true;
                    else if (dfs == 0) draw = true;
                    if (win) break;
                }
                if (win) ans = 1;
                else if (draw) ans = 0;
                else ans = 2;
            } else {
                boolean win = false, draw = false;
                for (int next : g[b]) {
                    if (next == 0) continue;
                    int dfs = dfs(k + 1, a, next);
                    if (dfs == 2) win = true;
                    else if (dfs == 0) draw = true;
                    if (win) break;
                }
                if (win) ans = 2;
                else if (draw) ans = 0;
                else ans = 1;
            }
        }
        f[k][a][b] = ans;
        return ans;
    }
}
